/*
day83
2019.11.19
*/

#include<stack>
#include<stdlib.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
 
class BSTIterator {
	
private:
	stack<TreeNode *> sta;
	TreeNode *cur;
public:
    BSTIterator(TreeNode* root) {
        cur=root;
        if(!sta.empty()) sta.pop();
    }
    
    /** @return the next smallest number */
    int next() {
    	int num;
        if( hasNext() )
        {
        	while(cur)
        	{
        		sta.push(cur);
        		cur=cur->left;
			}
			cur=sta.top();
			sta.pop();
			
		}
		else
		{
			return -1;
		}
		
		num=cur->val;
		if(cur->right)
		{
			cur=cur->right;
		}
		return num;
    }
    
    /** @return whether we have a next smallest number */
    bool hasNext() {
        if( sta.empty() ) return false;
    }
};


int main()
{
	return 0;
}
/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator* obj = new BSTIterator(root);
 * int param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */
